论文笔记04：A Heterogeneity-Aware Task Scheduler for Spark

发表于2018

一、解决的问题

大数据平台的应用没有关注到多维度的异构场景，导致在调度资源的时候，应用和硬件特性之间存在着本质上的不匹配问题。

二、提出的方法

2.1 创新点

提出了一种异构感知的任务调度系统——RUPAM，同时考虑任务级别的资源特征和硬件层面的特征，还能够保持数据本地化。RUPAM使用一种简单但高效的启发式去决定主导型的调度因素，将一个任务放置到特定的stage上。

2.2 结果

RUPAM对于Spark标准的调度器来说提升了62.3%的性能

三、背景

Spark调度

当前的Spark分为两个级别的调度：

• 应用级别调度：通常使用一些集群管理器来实现，例如内置的standalone集群管理器和外部的Mesos、YARN等，这些管理器通常会抽象硬件属性为CPU核数和内存大小。最主要的局限性体现在这些资源管理器不能够动态地满足应用的需求。
• 任务级别调度：当前的任务调度器只是将一个任务分配给一个CPU的核上，只考虑了数据本地化的因素。现有的异构性感知调度程序仅关注底层节点的异构性，并且通常假设同一Map / Reduce阶段中的所有任务具有相同的特征，如我们所示，并不总是成立。

前置研究

为了评估当前Spark的调度器，进行了了一些实验，通过这些实验得到的结论：

• 在单个应用上的不同stage的资源利用率是不同的：当前Spark调度器只是静态地将CPU核和存储器的一部分分配给给定应用程序（如当前调度程序中的情况）而没有考虑所需资源中的这种多样性和不一致性。
• 单个stage存在任务偏差：当前异构感知调度器假设同一个stage上任务有着相似的特征，表现性能也是相同的。

这些实验表明，即使在应用程序生命周期内，Spark应用程序也可能需要不同的资源， 其中的任务也具有不同的特征。

四、设计

A. 系统架构

RUPAM是一种任务级别的调度器，与应用级别和作业级别的调度器一起工作。

• Resource Monitor(RM)：资源监控器，负责系统资源的实时监控。它有一个运行在Spark的Master和Worker的监视器，收集器报告每个节点上资源的使用情况，例如CPU、内存、网络、I/O和GPU等。监视器负责从这些节点上收集和记录这些信息。还能够拓展收集资源性能上的更多信息。
• Task Manager (TM)：任务管理器，跟踪任务资源使用情况以确定任务的任何资源瓶颈。
• Dispatcher：实现RUPAM的主要逻辑，例如决定启动每个节点上executor的大小，将每个任务匹配合适的节点，对于特定节点启动任务的数量，基于多个维度调度任务。

利用TM和Dispatcher来取代Spark内置的TaskScheduler，不单单考虑数据本地化，而是同时考虑任务和节点的资源特性来调度任务。

B. 实时资源监控和任务监控

对于同一个任务的运行每个阶段的瓶颈期可能是不一样的，这样在任务整个生命周期上跟踪节点的资源使用情况为了低延迟来决定将任务分配到最优的节点上进行执行。

1. 资源监控：

   RUPAM利用心跳机制周期性地获取更多维度的硬件信息，使用一个对每个类型资源的优先队列。RUPAM只需要将节点中的一小部分进行排序，并且在下一轮调度的时候清空队列。通过这样的方式，能够保持较小的队列来降低排序过程的时间复杂度。

2. 任务监控：

   为了给定的节点选择一个合适的任务，RUPAM也需要根据任务的特性来进行决策。RUPAM使用一个数据库来存储周期性的数据中心的任务特性。为了将分辨在同一个stage资源需求的不同，TM为每种类型的资源保持一个队列。为了解决如何管理频繁的数据库操作，RUPAM使用一个帮助线程来辅助。

C. 任务调度

优化目标是：最小化对所有机器的所有任务的总执行时间

当前最流行的解决方法是列表调度算法，这是一种贪心算法，可以将任务映射到可用的机器而不会引入空闲时间。由于列表调度提供了具有良好的理论界限的实际解决方案，RUPAM采取了一种基于贪心的启发式算法。考虑的因素有：

• 硬件节点的容量（SSD,GPU）
• 每个任务的资源消耗
• 节点中每个资源的资源争用
• 运行在同一节点的任务数量
• 数据本地化

1. 调度策略

Dispatcher在task队列和资源队列的帮助下匹配任务，在RM填充资源队列之后，RUPAM以轮询的方式一次从每个资源队列中取出一个节点，以确保没有任何单一资源类型的任务饥饿。这种启发式贪心策略找到一个具有最佳容量和最低争用资源R的节点N，然后将N调度到任务T，其中R作为其先前运行中的瓶颈，如今N为T提供了最佳位置。RUPAM没有尝试对每个任务寻找一个全局最优的调度策略，因为这样可能会造成一个比较大的调度延迟，效果可能适得其反。将任务“锁定”到提供最佳观察性能的节点上，还可以防止由于任务特征的临时波动而在节点之间来回移动任务。

2. 资源分配

Spark在启动executor的时候会为其设置一个固定的CPU核数和内存，这种静态的配置其实是低效的。

• 首先，在异构环境下，节点拥有不同的内存大小和CPU核数；
• 第二，基于一个节点上的CPU核数来决定任务的slot其实是不准确的；
• 通过超提交一些具有空闲资源的节点和用适当的任务匹配节点，RUPAM可以重叠具有不同资源需求的任务。

3. 落后的任务（Straggler）和任务的重定位

为了弥补Dispatcher可能存在的次优决策，RUPAM还与最近引入的Spark推测执行系统一起工作，以在可用节点中启动Straggler的副本。当完成的任务数量达到一个阈值（默认是总数的75%），该推测系统就会搜索那些耗时超过已完成任务平均执行时间的一个系数的任务并且将其标记为Straggler任务。Straggler的副本将会在下一个可用节点上进行计算。除了被Spark检测为标准Straggler之外，RUPAM同样也会根据异构环境检测Straggler。

为了避免JVM中的OOM异常，RUPAM还采取了一种激进地策略检测内存的straggler。首先，只要RM检测到一个节点的可用内存较低的时候，它就发送消息给TM，并且通过检测当前正在运行的任务，TM标记那些占用较多内存的任务为Straggler，并终止这些任务。在标记之后，将这些任务的副本发送到TM，TM会根据这些任务的特性来确定其瓶颈并且将其再次放入任务队列。Dispatcher又可以再次将这些任务分配到适合的闲置节点上。

五、目标和设定

设定

每台机器上处理任务的时间根据机器变化

优化目标

最小化最大完工时间